"""
LeetCode 热题

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序
"""

from collections import Counter


class Solution(object):
    def findAnagrams(self, s, p):
        """
        寻找字符串 s 中所有 p 的异位词的起始索引。

        参数:
        s: 字符串，其中寻找异位词。
        p: 指定的异位词模式。

        返回:
        一个列表，包含所有 p 的异位词在 s 中的起始索引。
        """
        # 记录 p 中每个字符的出现次数
        p_count = Counter(p)
        # 记录当前窗口内字符的出现次数
        window_count = Counter()
        # 滑动窗口的大小
        window_size = len(p)
        # 用于记录所有异位词的起始索引
        result = []

        # 遍历字符串 s
        for i in range(len(s)):
            # 将当前字符加入窗口
            window_count[s[i]] += 1
            # 如果窗口大小超过 p 的长度，移除窗口最左边的字符
            if i >= window_size:
                # 如果最左边的字符在窗口中只出现了一次，则从窗口中移除该字符
                if window_count[s[i - window_size]] == 1:
                    del window_count[s[i - window_size]]
                else:
                    # 否则，减少该字符在窗口中的计数
                    window_count[s[i - window_size]] -= 1
            # 如果窗口内的字符计数与 p 的字符计数相同，则找到了一个异位词
            if window_count == p_count:
                # 将异位词的起始索引添加到结果列表中
                result.append(i - window_size + 1)

        return result

if __name__ == '__main__':
    a = Solution()
    print(a.findAnagrams("cbaebabacd", "abc"))
